import java.util.Arrays;
class LRUCache {

    public ListNode head;
    public ListNode tail;
    public int capacity;
    public Map<Integer, ListNode> map;

    class ListNode {
        public int key;
        public int value;
        ListNode pre;
        ListNode next;

        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.head = new ListNode(-1, -1);
        this.tail = new ListNode(-1, -1);
        this.head.next = this.tail;
        this.tail.pre = this.head;
        this.map = new HashMap<>();
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            deleteNode(node);
            insertHead(node);
            return node.value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // 有的话查找，更新值，头插；
            ListNode node = map.get(key);
            node.value = value;
            deleteNode(node);
            insertHead(node);
            map.put(key, node);
        } else {
            // 没有的话，检查容量，不够的话删除最后一个元素；头插；
            if (map.size() == this.capacity) {
                ListNode node = deleteLast();
                map.remove(node.key);
            }
            ListNode node = new ListNode(key, value);
            insertHead(node);
            map.put(key, node);
        }
    }

    private void deleteNode(ListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void insertHead(ListNode node) {
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    private ListNode deleteLast() {
        ListNode last = tail.pre;
        tail.pre = last.pre;
        last.pre.next = tail;
        return last;
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
